10288. Купоны

Имеется n разнотипных купонов и бесконечное количество закрытых коробок. В каждой коробке лежит один купон некоторого типа. Из каждой коробки с равной вероятностью можно извлечь купон любого типа. Какое ожидаемое количество коробок необходимо открыть, чтобы иметь хотя бы по одному купону каждого типа?

Вход. Каждая строка содержит число n (1 £ n £ 33), количество типов купонов.

Выход. Для каждого значения n вывести ожидаемое число коробок, которое надо открыть, чтобы иметь купоны всех типов. Если искомое число коробок целое, то вывести его. Если результат не целый, то вывести его целую часть, пробел, и дробную часть как показано в примере. Дробную часть результата представлять несократимой дробью.

Пример входа

2

5

17

Пример выхода

3

   5

11 --

   12

   340463

58 ------

   720720

РЕШЕНИЕ

вероятность

Анализ алгоритма

Предположим, что у Вас уже имеется n – k разных купонов. Обозначим через a_k ожидаемое количество коробок, которое следует открыть для того чтобы собрать недостающие k разных купонов. С вероятностью (n – k) / n купон в следующей коробке будет бесполезным, а с вероятностью k / n он будет того типа, которого у Вас еще нет. Имеем соотношение:

a_k = (1 + a_k) * + (1 + a_k-1) * ,

a₀ = 0

Раскроем скобки и выразим a_k через a_k-1:

a_k = + a_k-1

Рекуррентность можно расписать в виде:

a_k = + a_k-1 = + + a_k-2 = + + + a_k-3 = … =

= + + + … + + a₀ = n *

Ответом задачи будет значение a_n – ожидаемое количество коробок, которое следует открыть для того чтобы собрать недостающие n разных купонов:

a_n = n *

Для вывода результата в требуемом формате остается реализовать суммирование при помощи рациональных чисел. Для сокращения дробей будем использовать функцию gcd, вычисляющую наибольший общий делитель.

Пример

a₂ = 2 * (1 + ) = 3,

a₃ = 3 * (1 + + ) = 3 + + 1 = .

Реализация алгоритма

В структуре RatNumber храним рациональное число: числитель x и знаменатель y.

struct RatNumber

{

long long x,y;

} c, temp;

Функция gcd вычисляет наибольший общий делитель.

long long gcd(long long a, long long b)

{

return (!b) ? a : gcd(b,a % b);

}

Сложение рациональных чисел a и b. Возвращаемая сумма является несократимой дробью.

struct RatNumber add(struct RatNumber a,struct RatNumber b)

{

struct RatNumber res;

res.x = a.x*b.y + a.y*b.x;

res.y = a.y * b.y;

d = gcd(res.x,res.y);

if (d)

{

res.x /= d;res.y /= d;

}

return res;

}

Функция digits находит количество знаков числа x.

int digits(long long x)

{

if (x < 10) return 1;

return digits(x/10)+1;

}

Основной цикл программы. Читаем входное значение n.

while(scanf("%d",&n) == 1)

{

c.x = 0; c.y = 1; temp.x = 1;

Вычисление суммы c = n *

for(i=1;i<=n;i++)

{

temp.y = i;

c = add(c,temp);

}

c.x = n*c.x;

d = gcd(c.x,c.y);

c.x /= d; c.y /= d;

d = c.x / c.y;

c.x -= d*c.y;

Переменная d содержит целую часть результата c. Если знаменатель результата равен 1, то выводим только числитель. Иначе форматируем вывод ответа как показано в условии задачи.

if (c.y > 1)

{

for(i=0;i<=digits(d);i++) printf(" ");

printf("%lld\n",c.x);

printf("%lld ",d);

for(i=0;i<digits(c.y);i++) printf("-"); printf("\n");

for(i=0;i<=digits(d);i++) printf(" ");

printf("%lld\n",c.y);

}

else printf("%lld\n",d);

}